
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2427. -- [HAOI2010]软件安装 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2427: [HAOI2010]软件安装</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>128 MB<br><span class=green>Submit: </span>42&nbsp;&nbsp;<span class=green>Solved: </span>11<br>[<a href='submitpage.php?id=2427'>Submit</a>][<a href='problemstatus.php?id=2427'>Status</a>][<a href='bbs.php?id=2427'>Discuss</a>]</center><h2>Description</h2><div class=content><p><b style="mso-bidi-font-weight:normal"><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">现在我们的手头有</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">N</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">个软件，对于一个软件</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">i</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">，它要占用</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">W<sub>i</sub></span><span lang="RU" style="font-size:
12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">的磁盘空间，它的价值为</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">V<sub>i</sub></span><span lang="RU" style="font-size:
12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">。我们希望从中选择一些软件安装到一台磁盘容量为</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">M</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">计算机上，使得这些软件的价值尽可能大（即</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">V<sub>i</sub></span><span lang="RU" style="font-size:
12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">的和最大）。</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA"><br />
<br />
</span><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">但是现在有个问题：软件之间存在依赖关系，即软件</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">i</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">只有在安装了软件</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">j</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">（包括软件</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">j</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">的直接或间接依赖）的情况下才能正确工作（软件</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">i</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">依赖软件</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">j)</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">0</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">。</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA"><br />
<br />
</span><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">我们现在知道了软件之间的依赖关系：软件</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">i</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">依赖软件</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">D<sub>i</sub></span><span lang="RU" style="font-size:
12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">D<sub>i</sub>=0</span><span lang="RU" style="font-size:
12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">，这时只要这个软件安装了，它就能正常工作。</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA"><br style="mso-special-character:line-break" />
<br style="mso-special-character:line-break" />
</span></b></p>
<p></p></div><h2>Input</h2><div class=content><p><b style="mso-bidi-font-weight:normal"><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">第</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">1</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">行：</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">N, M</span><span lang="RU" style="font-size:12.0pt;
font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:宋体;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"> </span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA"><span style="mso-spacerun:yes">&nbsp;</span></span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">（</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">0&lt;=N&lt;=100, 0&lt;=M&lt;=500</span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">）</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA"><br />
</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;
mso-fareast-font-family:宋体;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:ZH-CN;
mso-bidi-language:AR-SA"><span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">第</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">2</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">行：</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">W<sub>1</sub>, W<sub>2</sub>, ... W<sub>i</sub>, ..., W<sub>n</sub> </span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:ZH-CN;
mso-bidi-language:AR-SA">（</span><span lang="RU" style="font-size:12.0pt;
font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">0&lt;=W<sub>i</sub>&lt;=M</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
宋体;color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"> </span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">）</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA"><br />
</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;
mso-fareast-font-family:宋体;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:ZH-CN;
mso-bidi-language:AR-SA"><span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">第</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">3</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">行：</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">V<sub>1</sub>, V<sub>2</sub>, ..., V<sub>i</sub>, ..., V<sub>n</sub> </span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;
mso-fareast-font-family:宋体;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:ZH-CN;
mso-bidi-language:AR-SA"><span style="mso-spacerun:yes">&nbsp;</span></span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">（</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">0&lt;=Vi&lt;=1000</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
宋体;color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"> </span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">）</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA"><br />
</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;
mso-fareast-font-family:宋体;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:ZH-CN;
mso-bidi-language:AR-SA"><span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">第</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">4</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">行：</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">D<sub>1</sub>, D<sub>2</sub>, ..., D<sub>i</sub>, ..., D<sub>n</sub></span><sub><span lang="RU" style="font-size:12.0pt;font-family:
&quot;Times New Roman&quot;;mso-fareast-font-family:宋体;color:black;background:white;
mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:
ZH-CN;mso-bidi-language:AR-SA"> </span></sub><span style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">（</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">0&lt;=D<sub>i</sub>&lt;=N, D<sub>i</sub>&ne;i</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
宋体;color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"> </span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;;mso-bidi-font-family:&quot;Times New Roman&quot;;
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">）</span><span lang="RU" style="font-size:12.0pt;font-family:&quot;Times New Roman&quot;;mso-fareast-font-family:
&quot;Times New Roman&quot;;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA"><br style="mso-special-character:line-break" />
<br style="mso-special-character:line-break" />
</span></b></p>
<p></p></div><h2>Output</h2><div class=content><p class="MsoNormal" style="margin-left:18.0pt;mso-para-margin-left:1.5gd"><b><span class="Apple-style-span" style="font-weight: normal; "><b style="mso-bidi-font-weight:normal"><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-bidi-font-family:宋体;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">一个整数，代表最大价值。</span></b></span></b></p>
<p></p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3 10<br />
5 5 6<br />
2 3 4<br />
0 1 1 </span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>5</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Day2'>Day2</a></p></div><center>[<a href='submitpage.php?id=2427'>Submit</a>][<a href='problemstatus.php?id=2427'>Status</a>][<a href='bbs.php?id=2427'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
